import java.util.*;
class Triplet{//定义一个类Triplet - 用于存储稀疏矩阵中非零元素的信息
    //非零元素在稀疏矩阵中的位置
    int row;//行号
    int col;//列号

    int val;//非零元素的值

    public Triplet(int row,int col,int val){//构造方法
        this.row = row;
        this.col = col;
        this.val = val;
    }
}

class SparseMatrix{//定义一个类SparseMatrix - 用于存储稀疏矩阵的信息，并相应的方法
    //成员变量
    //定义一个HashMap,名为matrix - 用于存储稀疏矩阵中非零元素的信息
    //其中Key表示第k个非零元素（也表示该非零元素在所有非零元素中的位置顺序）Value表示每个非零元素的信息
    HashMap<Integer,Triplet> matrix;
    int rows;//稀疏矩阵的行数
    int cols;//稀疏矩阵的列数
    int num;//稀疏矩阵中非零元素个数

    //构造方法1
    public SparseMatrix(HashMap<Integer,Triplet> matrix,int rows,int cols,int num){
        this.matrix = matrix;
        this.rows = rows;
        this.cols = cols;
        this.num = num;
    }

    //构造方法2 - 用二维数组表示的稀疏矩阵进行初始化
    public SparseMatrix(int[][] a){
        matrix = new HashMap<Integer,Triplet>();//新建一个HashMap，用于存储矩阵中非零元素的信息
        rows = a.length;//矩阵的行数等于二维数组的行数（一维数组的个数）
        cols = a[0].length;//矩阵的列数等于二维数组中每一行的元素个数
        int count = 0;//定义一个计数器，用于计算稀疏矩阵中非零元素的个数
        //遍历二维数组中的每个元素
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if(a[i][j]!=0){//当检测到数组中元素的不为零时，将其信息存储到HashMap中
                    //为非零元素实例化一个Triplet，并放到HashMap中，Key表示该非零元素为稀疏矩阵中的第k个非零元素
                    matrix.put(count,new Triplet(i,j,a[i][j]));
                    count++;//计数器+1
                }
            }
        }
        num = count;//保存稀疏矩阵中非零元素的个数
    }

    //输出稀疏矩阵 - 用于输出整个稀疏矩阵
    public void printSparseMatrix(){
        int count = 0;//定义一个计数器，用于记录已经输出的非零元素的个数
        //循环遍历稀疏矩阵中的每一个位置
        for (int i = 0; i < rows; i++) {//行
            for (int j = 0; j < cols; j++) {//列
                if(count<num){//非零元素还没输出完毕
                    Triplet triplet = matrix.get(count);//获取稀疏矩阵中的非零元素
                    //当该位置上的元素不为零时，输出非零元素
                    if(i==triplet.row && j==triplet.col){
                        System.out.print(triplet.val+" ");
                        count++;//已输出的非零元素个数+1
                        continue;//跳出本次循环，继续输出下一个元素
                    }
                }
                //当该位置上的元素为零时，输出0
                System.out.print(0+" ");//
            }
            System.out.println();
        }
    }

    //add方法 - 实现两个稀疏矩阵相加
    //定义一个add方法，参数为要相加的另一个稀疏矩阵，返回类型为SparseMatrix
    public SparseMatrix add(SparseMatrix B){
        try {
            if(rows!= B.rows || cols!=B.cols){//当两个矩阵的阶数不同时，抛出异常
                throw new IllegalArgumentException();
            }
        }catch (Exception exp){//接收异常
            System.out.println("两矩阵阶数不同，无法相加！");//输出异常原因
            return null;//返回null
        }


        //创建一个HashMap - 用于存储稀疏矩阵相加后得到的新矩阵的非零元素
        HashMap<Integer,Triplet> sum = new HashMap<Integer,Triplet>();
        HashMap<Integer,Triplet> a = this.matrix;//将第一个矩阵的引用赋给a
        HashMap<Integer,Triplet> b = B.matrix;//将第二个矩阵的引用赋给b

        int n1 = 0;//计数器n1 - 用于记录a中非零元素个数的使用情况
        int n2 = 0;//计数器n2 - 用于记录b中非零元素个数的使用情况
        int n3 = 0;//计数器n3 - 用于记录相加所得的稀疏矩阵(sum)中非零元素的个数

        //当两个矩阵的HashMap中Key对应的Value不为空时，说明矩阵中仍有非零元素没加到sum中
        while (b.get(n2)!=null ||a.get(n1)!=null) {
            //当n2等于第二个矩阵中非零元素的个数时
            //说明第二个矩阵中的非零元素已经全部加到sum中，剩下第一个矩阵中的非零元素没加
            if(n2== B.num){
                sum.put(n3,a.get(n1));//将第一个矩阵中的非零元素加到sum中
                n3++;
                n1++;
            }else if (n1==num){//同理，当第一个矩阵中非零元素全部加完，而第二个矩阵中仍有非零元素没加到sum中时
                sum.put(n3,b.get(n2));//将第二个矩阵中的非零元素加到sum中
                n3++;
                n2++;
            } else if (b.get(n2).row < a.get(n1).row ||
                    (b.get(n2).col < a.get(n1).col && b.get(n2).row == a.get(n1).row)){
                //当第二个矩阵的非零元素的位置在第一个矩阵的非零元素之前时，先把第二个矩阵中的非零元素加sum中
                sum.put(n3, b.get(n2));
                n2++;
                n3++;
            } else if (b.get(n2).row == a.get(n1).row &&
                    b.get(n2).col == a.get(n1).col) {//当两个矩阵中的非零元素位置相同时
                //获得该位置上两个非零元素的和，并把位置信息和元素值一起存到s中
                Triplet s = new Triplet(a.get(n1).row, a.get(n1).col, b.get(n2).val + a.get(n1).val);
                sum.put(n3, s);//把s添加到sum中
                n3++;
                n1++;
                n2++;
            } else if (b.get(n2).row > a.get(n1).row ||
                    (b.get(n2).col > a.get(n1).col && b.get(n2).row == a.get(n1).row)) {
                //当第二个矩阵的非零元素的位置在第一个矩阵的非零元素之后时，先把第一个矩阵中的非零元素加sum中
                sum.put(n3, a.get(n1));
                n1++;
                n3++;
            }
        }
        //用获得的sum、行数、列数和非零元素个数实例化一个稀疏矩阵类的对象并返回
        return (new SparseMatrix(sum,rows,cols,n3));
    }

    //search方法 - 用于找到位于第r行、第c列上的元素在HashMap中对应的Key
    public Integer searchKey(int r,int c){
        for (int i = 0; i < num; i++) {//根据Key遍历HashMap中的元素
            if(matrix.get(i).row==r && matrix.get(i).col==c){//当存在元素位于于第r行、第c列时
                return i;//返回对应的Key
            }
        }
        return -1;//当不存在第r行第c列的元素时，返回-1
    }

    //mul方法 - 实现稀疏矩阵相乘
    //定义一个mul方法，参数为要相乘的另一个稀疏矩阵，返回类型为SparseMatrix
    public SparseMatrix mul(SparseMatrix B){
        try {
            if(cols!= B.rows){//当第一个矩阵的列数不等于第二个矩阵的行数时，两矩阵不匹配，无法相乘
                throw new IllegalArgumentException("两矩阵的行数和列数不匹配，无法相乘！");//抛出异常
            }
        }catch (Exception exp){//接收异常
            System.out.println("两矩阵的行数和列数不匹配，无法相乘！");//输出异常原因
            return null;//返回null
        }

        int count = 0;//定义一个计数器 - 用于记录相乘得到的矩阵中非零元素的个数
        //新建一个稀疏矩阵类的对象，用于存放两个矩阵相乘后的结果
        SparseMatrix Mul = new SparseMatrix(new HashMap<Integer,Triplet>(),rows,B.cols,count);

        HashMap<Integer,Triplet> a = this.matrix;//将第一个矩阵的引用赋给a
        HashMap<Integer,Triplet> b = B.matrix;//将第二个矩阵的引用赋给b
        int n1 = 0;//计数器n1 - 用于记录a中非零元素个数的使用情况

        //遍历a中的非零元素
        while(a.get(n1)!=null){
            //记录a中当前非零元素的行数(r1)和列数(c1)
            int r1 = a.get(n1).row;
            int c1 = a.get(n1).col;
            int n2 = 0;//计数器n2 - 用于记录b中非零元素个数的使用情况

            //遍历b中的非零元素
            while(b.get(n2)!=null){
                //记录b中当前非零元素的行数(r2)和列数(c2)
                int r2 = b.get(n2).row;
                int c2 = b.get(n2).col;

                //由于稀疏矩阵的非零元素在HashMap中存储的时候Key是按照元素的位置排列的
                //所以如果b的第一个非零元素就在a当前的非零元素之后，说明b中不会再有元素可以和a中当前的非零元素相乘
                //因此，直接跳过a中当前非零元素对b中非零元素的遍历
                if(c1<r2||(r1<c2 && c1==r2)){
                    break;
                }else if (c1==r2){//当a中当前非零元素的列数和b中非零元素的行数相同时，执行相乘
                    //调用searchKey()方法，判断当前位置上是否已经存在元素并获取其在HashMap中对应Key
                    int pos = Mul.searchKey(r1,c2);
                    if(pos!=-1){//如果pos不为-1，说明该位置存在元素，直接将乘积加到原来元素的值上
                        Mul.matrix.get(pos).val+=a.get(n1).val*b.get(n2).val;
                    }else {//否则说明该位置上没有元素，则将该位置上相乘得到的结果放到HashMap中
                        Mul.matrix.put(count,new Triplet(r1,c2,a.get(n1).val*b.get(n2).val));
                        count++;//Mul中非零元素个数+1
                    }
                    break;
                }else {//b的第一个非零元素在a当前的非零元素之前，则继续向后遍历b中的非零元素
                    n2++;
                }
            }
            //a中当前元素对b中非零元素的遍历结束
            n1++;//由a中下一个非零元素对b中的非零元素进行遍历
        }
        Mul.num = count;//记录Mul中非零元素个数
        return Mul;//返回相乘结果Mul
    }
}

//测试稀疏矩阵
public class TestSparseMatrix {
    public static void main(String[] args) {
        //下面分别用二维数组定义三个矩阵a、b、c
        int[][] a = {
                {0,0,1,0},
                {0,0,0,0},
                {2,0,5,0},
                {0,0,0,1}};
        int[][] b ={
                {0,0,0,0},
                {0,0,1,2},
                {1,0,0,0},
                {0,5,0,0}};
        int[][] c ={
                {0,0,0},
                {0,0,2},
                {1,0,0},
                {0,0,0}};

        //a、b、c分别通过构造方法2实例化三个稀疏矩阵对象A、B、C
        SparseMatrix A = new SparseMatrix(a);
        SparseMatrix B = new SparseMatrix(b);
        SparseMatrix C = new SparseMatrix(c);

        //稀疏矩阵的相加
        SparseMatrix sum = A.add(B);
        System.out.println("A+B:");
        sum.printSparseMatrix();
        System.out.println();

        //A和C矩阵阶数不同，会抛出异常
        SparseMatrix Sum = A.add(C);
        System.out.println("A+C:");
        System.out.println(Sum);
        System.out.println();

        //稀疏矩阵的相乘
        SparseMatrix mul = A.mul(B);
        System.out.println("A*B:");
        mul.printSparseMatrix();
        System.out.println();

        SparseMatrix Mul = A.mul(C);
        System.out.println("A*C:");
        Mul.printSparseMatrix();
        System.out.println();
    }
}
